#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAXLINES 5000 /*进行排序的最大文本行数*/
char * lineptr[MAXLINES]; /*指向文本行的指针数组*/
#define MAXLEN 1000 /*每个输入文本行的最大长度*/

int readlines(char* lineptr[],int nlines,char* lines[]);
void writelines(char* lineptr[],int nlines);

/*swap函数, 交换v[i]和v[j]*/
void swap(char*v[],int i,int j){
    char* tmp = v[i];
    v[i] = v[j];
    v[j] = tmp;
}

/*qsrot函数, 按照递增顺序对 v[left] ... v[right]进行排序*/
void myqsort(char* v[],int left,int right){
    int i, last;

    if(left >=right){
        return;/*如果数组元素的个数小于2,则返回*/
    }
    swap(v,left, (left+right)/2);
    last = left;
    for(i=left+1;i<=right;i++){
        if(strcmp(v[i], v[left]) < 0){
            swap(v, ++last, i);
        }
    }
    swap(v,left,last);
    myqsort(v,left, last-1);
    myqsort(v,last+1,right);
}

/*对输入的文本行进行排序*/
int main(){
    int nlines;/*读取的输入行数目*/
    char *lines[MAXLINES];
    for(int i=0;i<MAXLINES;i++){
        lines[i]=(char*)malloc(MAXLEN);
    }
    if((nlines = readlines(lineptr, MAXLINES, lines)) >= 0){
        myqsort(lineptr,0,nlines-1);
        writelines(lineptr, nlines);
        return 0;
    }else{
        printf("error: input too big to sort\n");
        return 1;
    }
}

/*mygetline函数, 将一行读入到s中并返回长度*/
int mygetline(char*s,int lim){
    int c,i;
    for(i=0;i<lim-1&&(c=getchar()) != EOF && c!='\n';++i){
        s[i]=c;
    }
    if(c=='\n'){
        s[i]=c;
        ++i;
    }
    s[i]=0;
    return i;
}

/*readlines函数, 读取输入行*/
/*将输入的文本行存储到由main函数提供的一个数组中,而不是存储到alloc分配的存储空间中, 看看运行速度会快多少*/
int readlines(char* lineptr[], int maxlines, char* lines[]){
    int len,nlines;
    char* p,line[MAXLEN];
    nlines = 0;
    while ((len = mygetline(line,MAXLEN))>0)
    {
        if(nlines>=maxlines){
            return -1;
        }else{
            p = lines[nlines];
            line[len-1] = 0;/*删除换行符*/
            strcpy(p,line);
            lineptr[nlines++]=p;
        }
    }
    return nlines;
}

/*writelines函数; 写输出行*/
void writelines(char* lineptr[], int nlines){
    int i;
    for(i=0;i<nlines;i++){
        printf("%s\n", lineptr[i]);
    }
}

